import java.util.LinkedList;



public class DistanceCacheMegaMatrix implements DistanceCache 
{
	boolean[][] visitedMatrix;
	
	boolean[][] wallMatrix;
	boolean[][] deadlocks;
	
//	int[][] goalOrderMatrix;
	
	short[][] closestGoal;
	
	short[][][][] playerDistance;
	short[][][][] boxDistance;
	Board board;
//	MoveRule isWall;
		
	Move.Direction[] legalMovesCache;
	
	public DistanceCacheMegaMatrix( Board board )
	{
		visitedMatrix = new boolean[ board.getXLength() ][ board.getYLength() ];
		wallMatrix = new boolean[ board.getXLength() ][ board.getYLength() ];
		
		closestGoal = new short[ board.getXLength() ][ board.getYLength() ];
		
//		goalOrderMatrix = new int[ board.getXLength() ][ board.getYLength() ];

		deadlocks = board.getDeadlockArray();
		
		for ( int x = 0; x < board.getXLength(); x++ )
		{
			for ( int y = 0; y < board.getYLength(); y++ )
			{
				wallMatrix[x][y] = board.getCellType(x, y).isWall();
			}
		}
		
		this.board = board;
		
//		isWall = new IsWall();
		
		playerDistance = new short[ board.getXLength() ][ board.getYLength() ][ board.getXLength() ][ board.getYLength() ];
		boxDistance = new short[ board.getXLength() ][ board.getYLength() ][ board.getXLength() ][ board.getYLength() ];
		
		long time = System.currentTimeMillis();
		
		
		for ( int xStart = 0; xStart < board.getXLength(); xStart++ )
		{
			for ( int yStart = 0; yStart < board.getYLength(); yStart++ )
			{
				for ( int xGoal = 0; xGoal < board.getXLength(); xGoal++ )
				{
					for ( int yGoal = 0; yGoal < board.getYLength(); yGoal++ )
					{
						playerDistance[xStart][yStart][xGoal][yGoal] = Short.MAX_VALUE;
						boxDistance[xStart][yStart][xGoal][yGoal] = Short.MAX_VALUE;
					}
				}	
			}
		}
		
		BFSPlayer( board.getPlayer().getX(), board.getPlayer().getY(), false );
		BFSPlayer( board.getPlayer().getX(), board.getPlayer().getY(), true );
		
		for ( int x = 0; x < board.getXLength(); x++ )
		{
			for ( int y = 0; y < board.getYLength(); y++ )
			{
				if ( playerDistance[board.getPlayer().getX()][board.getPlayer().getY()][x][y] == Short.MAX_VALUE )
				{
					wallMatrix[x][y] = true;
				}
				
//				if ( !board.getCellType(x, y).isWall() )
				if ( !wallMatrix[x][y] )
				{
					BFSPlayer( x, y, false );
					BFSPlayer( x, y, true );
				}
			}
		}
		
		/*
		 * Calculate closest goal from (x,y)
		 */
		for ( int x = 0; x < board.getXLength(); x++ )
		{
			for ( int y = 0; y < board.getYLength(); y++ )
			{
//				closestGoal[x][y] = (short) minimumBoxDistanceToGoal(board,  new CordImpl(x,y) );
				closestGoal[x][y] = (short) minimumBoxDistancePrivate( board , new CordImpl(x,y), board.getGoals() );
			}
		}
		

//		playerDistance[xStart][yStart][xGoal][yGoal] = 0;
//		counter++;
		if ( Client.PRINT_COMMENTS )
		{
			System.out.println("time to BFS megaMatrix = "+( System.currentTimeMillis()-time ));
		}
		
		
//		printFromCord( new CordImpl(2,3), true );
	}
	
//	private void printFromCord( Cord start, boolean box )
//	{
//        for ( int y = 0; y < board.getYLength(); y++ )
//        {
//        	for ( int x = 0; x < board.getXLength(); x++ )
//        	{
//				if ( wallMatrix[x][y] )
//				{
//					System.out.print( Board.CellType.Wall+"\t" );
//				}
//				else
//				{
//					if ( box )
//					{
//						System.out.print( getDistanceBox(start, new CordImpl( x,y ))+"\t" );
//					}
//					else
//					{
//						System.out.print( getDistancePlayer(start, new CordImpl( x,y ))+"\t" );
//					}
//					
//				}
//			}
//			System.out.println();
//		}
//	}
	
	private void clearVisitedMatrix()
	{
		for ( int x = 0; x < board.getXLength(); x++ )
		{
			for ( int y = 0; y < board.getYLength(); y++ )
			{
				visitedMatrix[x][y] = false;
			}
		}
	}
	
//	private int getLegalMoves( int x, int y )
//	{
//		for ( Move.Direction direction : Move.Direction.values() )
//		{
//			
//			
//		}
//	}
	
	public boolean existsCellAt( int x, int y )
	{
		boolean exists = true;
		
		exists &= 0 <= x;
		exists &= x < wallMatrix.length;
		
		exists &= 0 <= y;
		exists &= y < wallMatrix[0].length;
		
		return exists;
	}
	
	private static class BFSEntry
	{
		int x; 
		int y; 
		int currentDistance; 
		
		public BFSEntry( int x, int y, int currentDistance )
		{
			this.x = x;
			this.y = y;
			this.currentDistance = currentDistance;
		}
	}
	
	private void BFSPlayer( final int startX, final int startY, final boolean box )
	{
		
		clearVisitedMatrix();
		
		LinkedList<BFSEntry> queue = new LinkedList<BFSEntry>(); 
		
		queue.addLast(new BFSEntry( startX, startY, 0 ));
		
//		int iterations = 0;
//		
		while ( !queue.isEmpty() )
		{
			
//			System.out.println( "iterations="+iterations );
//			iterations++;
			
			BFSEntry entry = queue.removeFirst();
			int x = entry.x;
			int y = entry.y;
			int currentDistance = entry.currentDistance;
			
//			System.out.println("queue.size() = "+queue.size() +", x="+x+", y="+y+", distance="+currentDistance);

			if (box)
			{
				boxDistance[startX][startY][x][y] = (short) currentDistance;
			}
			else
			{
				playerDistance[startX][startY][x][y] = (short) currentDistance;
			}
			
			
			visitedMatrix[ x ][ y ] = true;
			
			
			for ( Move.Direction direction : Move.Direction.values() )
			{
				
				int newX = x+direction.getXDiff();
				int newY = y+direction.getYDiff();
				
//				System.out.println( "x="+currentX+", y="+currentY );
//				System.out.println( "direction="+direction);
//				System.out.println( "newX="+newX+", newY="+newY );
				
				if ( existsCellAt( newX, newY ) )
				{
					if ( !wallMatrix[newX][newY] && !visitedMatrix[newX][newY] )
					{
						if ( box && (!deadlocks[ newX ][ newY ]) )
						{
							queue.addLast(new BFSEntry( newX, newY, (currentDistance+1) ));
						}
						else if ( !box )
						{
							queue.addLast(new BFSEntry( newX, newY, (currentDistance+1) ));
						}
						
					}

				}
				
			}
		}	
		
	}
	
	@Override
	public int getDistancePlayer( Cord start, Cord goal )
	{
		return playerDistance[start.getX()][start.getY()][goal.getX()][goal.getY()];
	}
	
	@Override
	public int getDistanceBox( Cord start, Cord goal )
	{
		return boxDistance[start.getX()][start.getY()][goal.getX()][goal.getY()];
	}
	
//	private int minimumBoxDistanceToGoal( Board board, Cord start )
//	{
//		int min = Integer.MAX_VALUE;
//		boolean found = false;
//		
//		for ( int x = 0; x < board.getXLength(); x++ )
//		{
//			for ( int y = 0; y < board.getYLength(); y++ )
//			{
//				Cord goal = new CordImpl( x,y );
//				if (!found)
//				{
//					min = getDistanceBox(start, goal);
//					found = true;
//				}
//				else
//				{
//					min = Math.min( min , getDistanceBox(start, goal) );
//				}
//			}
//		}
//		
//		return min;
//	}
	
	private int minimumBoxDistancePrivate( Board board, Cord start, Cord[] goals )
	{
		int min = Integer.MAX_VALUE;
		
		boolean found = false;
		for( Cord goal : goals )
		{ 
			if (!found)
			{
				min = getDistanceBox(start, goal);
				found = true;
			}
			else
			{
				min = Math.min( min , getDistanceBox(start, goal) );
			}

		}
		
		return min;
	}
	
	@Override
	public int minimumBoxDistance( Board board, Cord start, Cord[] goals )
	{
		return closestGoal[ start.getX() ][ start.getY() ];
	}
	
	@Override
	public int minimumPlayerDistance( Board board, Cord start, Cord[] goals )
	{
		int min = Integer.MAX_VALUE;
		
		boolean found = false;
		for( Cord goal : goals )
		{ 
			if (!found)
			{
				min = getDistancePlayer(start, goal);
				found = true;
			}
			else
			{
				min = Math.min( min , getDistancePlayer(start, goal) );
			}

		}
		
		return min;
	}

}


//if ( wallMatrix[x][y] || visitedMatrix[x][y] )
//{
//	return;
//}
//
//playerDistance[startX][startY][x][y] = (short) currentDistance;
////playerDistance[currentX][currentY][startX][startY] = (short) currentDistance;
//visitedMatrix[ x ][ y ] = true;
//
////if ( !deadlocks[ currentX ][ currentY ] )
////{
////	boxDistance[startX][startY][currentX][currentY] = (short) currentDistance;
////}
////else
////{
////	boxMovable = false;
////}
//
//for ( Move.Direction direction : Move.Direction.values() )
//{
//	
//	int newX = x+direction.getXDiff();
//	int newY = y+direction.getYDiff();
//	
////	System.out.println( "x="+currentX+", y="+currentY );
////	System.out.println( "direction="+direction);
////	System.out.println( "newX="+newX+", newY="+newY );
//	
//	if ( existsCellAt( newX, newY ) )
//	{
////		if ( !wallMatrix[newX][newY] && !visitedMatrix[newX][newY] )
////		{
//			BFSPlayer( startX, startY, newX, newY, currentDistance+1, boxMovable );
////		}
//	}
//	
//}

//for ( Move move : board.getLegalMoves( new CordImpl( currentX,currentY ) , isWall) )
//{
//	if ( !visitedMatrix[ move.getX() ][ move.getY() ] )
//	{
//		BFSPlayer( startX, startY, move.getX(), move.getY(), currentDistance+1 );
//	}
//}	
